package offer2

/**
原题链接:
https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/

B站阿苏EEer
剑指 Offer 34. 二叉树中和为某一值的路径
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。

示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
*/
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func pathTarget(root *TreeNode, target int) [][]int {
	res := make([][]int, 0)
	path := make([]int, 0)

	var dfs func(root *TreeNode, target int, sum int)

	dfs = func(root *TreeNode, target int, sum int) {
		if root == nil {
			return
		}
		sum += root.Val
		path = append(path, root.Val)
		if root.Left == nil && root.Right == nil {
			if sum == target {
				temp := make([]int, len(path))
				copy(temp, path)
				res = append(res, temp)
			}
		}

		dfs(root.Left, target, sum)
		dfs(root.Right, target, sum)
		path = path[:len(path)-1]
	}

	dfs(root, target, 0)
	return res
}
